package org.basis.algorithm.tree;

import java.util.*;

/**
 * 二叉树的序列化和反序列化
 *
 * @author Mr_wenpan@163.com 2021/12/21 17:55
 */
public class SerializeAndReconstructTree {

    public static void main(String[] args) {

    }

    /**
     * 先序遍历序列化二叉树
     * # 表示空
     * _ 表示一个节点完毕
     */
//    public static String preOrderSerialize(TreeNode<Integer> head) {
//        if (head == null) {
//            return null;
//        }
//        Stack<TreeNode<Integer>> stack = new Stack<>();
//        stack.push(head);
//        StringBuffer buffer = new StringBuffer();
//        while (!stack.isEmpty()) {
//            TreeNode<Integer> pop = stack.pop();
//            buffer.append(pop.data).append("_");
//            if (pop.right != null) {
//                stack.push(pop.right);
//            } else {
//                // 空占位符 #
//                buffer.append("#_");
//            }
//            if (pop.left != null) {
//                stack.push(pop.left);
//            } else {
//                // 空占位符 #
//                buffer.append("#_");
//            }
//        }
//
//        return buffer.toString();
//    }

    /**
     * 先序遍历序列化一棵二叉树
     */
    public static String serialByPre(Node head) {
        if (head == null) {
            return "#!";
        }
        // 以!标识一个节点完毕
        String res = head.value + "!";
        res += serialByPre(head.left);
        res += serialByPre(head.right);
        return res;
    }

    /**
     * 反序列化先序遍历的二叉树
     */
    public static Node reconByPreString(String preStr) {
        String[] values = preStr.split("!");
        Queue<String> queue = new LinkedList<String>();
        for (int i = 0; i != values.length; i++) {
            queue.offer(values[i]);
        }
        return reconPreOrder(queue);
    }

    public static Node reconPreOrder(Queue<String> queue) {
        String value = queue.poll();
        if ("#".equals(value)) {
            return null;
        }
        // 从队列弹出一个数并构建为节点
        Node head = new Node(Integer.parseInt(value));
        // 构建该节点的左孩子
        head.left = reconPreOrder(queue);
        // 构建该节点的右孩子
        head.right = reconPreOrder(queue);
        return head;
    }

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            value = data;
        }
    }

}
